#include <iostream>
#include <string>
#include<cstring>
using namespace std;
 
const int Num = 26;             //每个节点需要保存26个字母
 
struct TrieNode
{
    bool Isword;                //判断是否是单词
    TrieNode* next[Num];
    TrieNode() :Isword(false)   //初始化
    {
        memset(next, NULL, sizeof(next));
    }
};
 
class Trie
{
public:
    Trie() { root = new TrieNode(); }
    void insert(string word);
    bool search(string word);
    void deleteTrie(TrieNode* root);
private:
    TrieNode* root;
};
 
void Trie::insert(string word)
{
    TrieNode* location = root;
    for (int i = 0; i < word.length();i++)
    {
        if (location->next[word[i] - 'a'] == nullptr)
        {
            TrieNode* temp = new TrieNode();
            location->next[word[i] - 'a']=temp;
        }
        location = location->next[word[i] - 'a'];
    }
    location->Isword = true;
}
 
bool Trie::search(string word)
{
    TrieNode* location = root;
    //while (word&&location)//注意location不能为空
    for (int i = 0; i < word.length()&&location;i++)
        location = location->next[word[i] - 'a'];
    return(location != NULL && location->Isword);
}
 
void Trie::deleteTrie(TrieNode* root)
{
    for (int i = 0; i < Num; i++)
    {
        if (root->next[i] != NULL)
        {
            deleteTrie(root->next[i]);
        }
    }
    delete root;
}
 
int main()                     //简单测试  
{
    Trie tree;
    int n;                      //输入n个单词在字典树中
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s;
        tree.insert(s);
    }
    string input;
    cout << "输入要检查的单词" << endl;
    cin >> input;
    cout << boolalpha << tree.search(input) << endl;//查找是否存在是个单词
}